Nhận xét, nếu (x,y) là nghiệm nguyên của phương trình đã cho thì (-x,y), (x,-y), (-x,-y) cũng là nghiệm, do đó ta chỉ cần quan tâm đến các nghiệm nguyên không âm.

Phương trình Pell x 2 − d y 2 = 1 {\displaystyle x^{2}-dy^{2}=1} luôn có nghiệm tầm thường là x=1, y=0. Do đó, ta chỉ quan tâm đến các nghiệm nguyên không âm và không tầm thường.

Một số điều kiện của d để có nghiệm

Định lý 1: Với mọi d không phải là số chính phương, phương trình x 2 − d y 2 = 1 {\displaystyle x^{2}-dy^{2}=1} luôn có nghiệm nguyên dương.

Định lý 2: Nếu d có ước nguyên tố dạng 4k+3 thì phương trình x 2 − d y 2 = − 1 {\displaystyle x^{2}-dy^{2}=-1} vô nghiệm.

Phương pháp sinh từ nghiệm nguyên dương nhỏ nhất

Nghiệm nguyên dương nhỏ nhất theo nghĩa: x,y >0 và x + y d {\displaystyle x+y{\sqrt {d}}} là nhỏ nhất.

Phương pháp này dùng để tìm tất cả các nghiệm nguyên dương của phương trình x 2 − d y 2 = 1 , {\displaystyle x^{2}-dy^{2}=1,} với d không phải là số chính phương.

Khi biết nghiệm nhỏ nhất của phương trình là (x1,y1), cho phép tìm ra tất cả các nghiệm nguyên dương còn lại theo công thức tổng quát:

x i + y i d = ( x 1 + y 1 d ) i . {\displaystyle x_{i}+y_{i}{\sqrt {d}}=(x_{1}+y_{1}{\sqrt {d}})^{i}.}

Công thức truy hồi tương đương:

x i + 1 = x 1 x i + d y 1 y i , {\displaystyle \displaystyle x_{i+1}=x_{1}x_{i}+dy_{1}y_{i},} y i + 1 = x 1 y i + y 1 x i . {\displaystyle \displaystyle y_{i+1}=x_{1}y_{i}+y_{1}x_{i}.}

Ví dụ:

Trong ví dụ trước x 2 − 2 y 2 = 1 {\displaystyle x^{2}-2y^{2}=1} , ta tìm ra nghiệm nhỏ nhất là (3,2). Tìm các nghiệm còn lại:

x 2 + y 2 2 = ( 3 + 2 2 ) 2 = 17 + 12 2 {\displaystyle x_{2}+y_{2}{\sqrt {2}}=(3+2{\sqrt {2}})^{2}=17+12{\sqrt {2}}} , suy ra nghiệm (17,12); x 3 + y 3 2 = ( 3 + 2 2 ) 3 = 99 + 70 2 {\displaystyle x_{3}+y_{3}{\sqrt {2}}=(3+2{\sqrt {2}})^{3}=99+70{\sqrt {2}}} , suy ra nghiệm (99,70).

Lời giải dựa trên phân số liên tục

Xem thêm bài phân số liên tục, xem thêm [2].

Định lý 1

Viết dãy các giản phân của d {\displaystyle {\sqrt {d}}} : h n k n {\displaystyle {\frac {h_{n}}{k_{n}}}} .

Biểu diễn liên phân số của d {\displaystyle {\sqrt {d}}} có dạng vô hạn tuần hoàn, gọi r là độ dài của 1 chu kì. Khi đó:

nếu r chẵn thì tất cả các nghiệm nguyên dương của phương trình x 2 − d y 2 = 1 {\displaystyle x^{2}-dy^{2}=1} là ( h n , k n {\displaystyle {h_{n}},{k_{n}}} ) là với n có dạng k ⋅ r − 1 {\displaystyle k\cdot r-1} ;nếu r lẻ thì tất cả các nghiệm nguyên dương của phương trình x 2 − d y 2 = 1 {\displaystyle x^{2}-dy^{2}=1} là( h n , k n {\displaystyle {h_{n}},{k_{n}}} ) với n có dạng 2 ⋅ t ⋅ r − 1 {\displaystyle 2\cdot t\cdot r-1} .

Ví dụ:

• Giải phương trình nghiệm nguyên dương:

x 2 − 2 y 2 = 1 {\displaystyle x^{2}-2y^{2}=1} .Biểu diễn liên phân số của 2 {\displaystyle {\sqrt {2}}} là: 2 = [ 1 ; 2 , 2 , 2 , 2 , … , ] {\displaystyle {\sqrt {2}}=[1;2,2,2,2,\,\ldots ,]} , biểu diễn này có chu kì r=1 lẻ, do đó nghiệm của phương trình là ( h n , k n {\displaystyle {h_{n}},{k_{n}}} ) với n có dạng 2 ⋅ t − 1 {\displaystyle 2\cdot t-1} , các giản phân ở vị trí lẻ.Dãy số gần nhất của 2 {\displaystyle {\sqrt {2}}} : 1 , 3 2 , 7 5 , 17 12 , 41 29 , 99 70 , 239 169 , 577 408 , 1393 985 , 3363 2378 , 8119 5741 , … , {\displaystyle 1,{\frac {3}{2}},{\frac {7}{5}},{\frac {17}{12}},{\frac {41}{29}},{\frac {99}{70}},{\frac {239}{169}},{\frac {577}{408}},{\frac {1393}{985}},{\frac {3363}{2378}},{\frac {8119}{5741}},\,\ldots ,} .Chú ý dãy số trên được bắt đầu với số thứ tự bằng 0.Lấy các phân số ở vị trí lẻ ta được nghiệm nguyên dương của phương trình x 2 − 2 y 2 = 1 {\displaystyle x^{2}-2y^{2}=1} là: (3,2) (17,12), (99,70), (577,408), (3363,2378),...và tất nhiên cả nghiệm tầm thường là (1,0).

• Giải phương trình nghiệm nguyên dương:

x 2 − 13 y 2 = 1 {\displaystyle x^{2}-13y^{2}=1} . Biểu diễn liên phân số của 1 3 {\displaystyle {\sqrt {1}}3} là: 1 3 = [ 3 ; 1 , 1 , 1 , 1 , 6 , 1 , 1 , 1 , 1 , 6 … , ] {\displaystyle {\sqrt {1}}3=[3;1,1,1,1,6,1,1,1,1,6\,\ldots ,]} , biểu diễn này có chu kì r=5 lẻ, các nghiệm cần tìm là ( h n , k n {\displaystyle {h_{n}},{k_{n}}} ) với n có dạng 10 ⋅ t − 1 {\displaystyle 10\cdot t-1} .Dãy giản phân của 1 3 {\displaystyle {\sqrt {1}}3} là (dãy này bắt đầu với số thứ tự là 0): 3 , 4 1 , 7 2 , 11 3 , 18 5 , 119 33 , 137 38 , 256 71 , 393 109 , 649 180 , 4287 1189 , … {\displaystyle 3,{\frac {4}{1}},{\frac {7}{2}},{\frac {11}{3}},{\frac {18}{5}},{\frac {119}{33}},{\frac {137}{38}},{\frac {256}{71}},{\frac {393}{109}},{\frac {649}{180}},{\frac {4287}{1189}},\ldots } .Với t=1, n=9, ta tìm ra nghiệm nguyên dương nhỏ nhất của phương trình đã cho: ( 649 , 180 ) {\displaystyle (649,180)} .

Định lý 2

Phương trình Pell x 2 − d y 2 = − 1 {\displaystyle x^{2}-dy^{2}=-1} có nghiệm khi và chỉ khi biểu diễn liên phân số của d {\displaystyle {\sqrt {d}}} có chu kì r lẻ và các nghiệm nguyên dương của phương trình sẽ là ( h n , k n ) {\displaystyle (h_{n},k_{n})} với n có dạng 2 ⋅ t ⋅ r − r − 1 {\displaystyle 2\cdot t\cdot r-r-1} .

Ví dụ:

• Giải phương trình nghiệm nguyên:

x 2 − 13 y 2 = − 1 {\displaystyle x^{2}-13y^{2}=-1} .Theo như phân tích ở trên, thì r=5, do đó các nghiệm nguyên dương của phương trình có dạng ( h 10 t − 6 , k 10 t − 6 ) {\displaystyle (h_{10t-6},k_{10t-6})} , với t=1 đó là cặp (18,5).

Dạng biểu diễn rút gọn và các thuật toán nhanh

Trong các bài toán cụ thể, ngay cả nghiệm nhỏ nhất cũng có thể rất lớn. Và trong nhiều trường hợp, người ta phải biểu diễn nó dưới dạng gọn hơn là:

x 1 + y 1 n = ∏ i = 1 t ( a i + b i n ) c i {\displaystyle x_{1}+y_{1}{\sqrt {n}}=\prod _{i=1}^{t}(a_{i}+b_{i}{\sqrt {n}})^{c_{i}}}

với các hệ số ai, bi, and ci nhỏ hơn rất nhiều (nếu so sánh với nghiệm nhỏ nhất).

Ví dụ, bài toán đàn gia súc Archimedes có thể giải quyết bằng cách dùng phương trình Pell, nhưng nghiệm nhỏ nhất của nó quá lớn, nếu viết hết nghiệm này ra giấy có thể đến 206545 chữ số. Và như thế phải viết nghiệm đó dưới dạng rút gọn:

x 1 + y 1 n = u 2329 , {\displaystyle x_{1}+y_{1}{\sqrt {n}}=u^{2329},}

với:

u = ( x 1 ′ + y 1 ′ 4729494 ) {\displaystyle u=(x'_{1}+y'_{1}{\sqrt {4729494}})}

và x 1 ′ {\displaystyle \scriptstyle x'_{1}} và y 1 ′ {\displaystyle \scriptstyle y'_{1}} lần lượt có 45 và 41 chữ số thập phân.

Chính xác hơn là:

u = ( 300426607914281713365 609 + 84129507677858393258 7766 ) 2 . {\displaystyle u=(300426607914281713365{\sqrt {609}}+84129507677858393258{\sqrt {7766}})^{2}.} (Lenstra 2002)Lỗi harv: không có mục tiêu: CITEREFLenstra2002 (trợ giúp).

Các phương pháp liên quan đến sàng toàn phương (quadratic sieve) (dùng trong phân tích số ra ước số nhỏ hơn (integer factoriaztion)), được dùng để tập hợp các mối quan hệ giữa các số nguyên tố trong trường số tổng quát hóa bởi √n, và kết hợp các mối quan hệ này nhằm tìm ra dạng biểu diễn của dạng số đó. Những thuật toán sử dụng phương trình Pell hiệu quả hơn các thuật toán dùng liên phân số rất nhiều; bởi vì hàm thời gian của các thuật toán dùng phương trình Pell không phải là các hàm đa thức. Sử dụng giả thiết Riemann tổng quát hóa (generalized Riemann hypothesis), ta ước lượng được thời gian:

exp ⁡ O ( log ⁡ N log ⁡ log ⁡ N ) , {\displaystyle \exp O({\sqrt {\log N\log \log N}}),}

với N = log n kích thước dữ liệu vào, đối với sàng toàn phương (Lenstra 2002)Lỗi harv: không có mục tiêu: CITEREFLenstra2002 (trợ giúp).